1. Field of the Invention
This invention relates to apparatus and methods for performing data-flow analysis for computer programs.
2. Background of the Invention
Data-flow analysis is a technique commonly used to determine values or properties at various points in a computer program. When performing a data-flow analysis, a program's control flow graph, made up of nodes and edges between nodes, may be used to determine where a particular value assigned to a variable might propagate. The information gathered by the data-flow analysis may be used by compilers to optimize the computer program.
One particular problem a data-flow analysis may attempt to solve is a variation of the “use-def” problem involving label variables. In this problem, a label variable is set to some number of values in some number of basic blocks. These are referred to as the “definitions” of the label variable. In other basic blocks, the label variable is the operand of indirect branches. These are referred to as the “uses” of the label variable. The problem is to discover which definitions of a label variable reach which uses of the label variable.
Initially, a compiler may assume that all possible definitions of a label variable reach all actual uses, and reflect this in a program's control flow graph. The problem may then be solved using a conventional data-flow algorithm. However, conventional dataflow algorithms define the inset of a node in the control flow graph as a join operation on the outsets of all of the node's predecessors. This means that a single pass of the conventional dataflow algorithm is likely to find an opportunity to reduce the control flow graph, but exercising that opportunity will expose other opportunities which will in turn require further executions of the algorithm. This is because, in a first pass of the algorithm, a definition of some label variable may have reached a use of that label variable on what was proven by the first pass to be an implausible edge. A second pass may further reduce the control flow graph which may in turn expose additional opportunities to reduce the control flow graph. Each of these executions (i.e., passes) is expensive in time.
In view of the foregoing, what are needed are apparatus and methods to more efficiently solve the “use-def” problem involving label variables.